|
In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too). This notion was introduced by . proved that all languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins. The basic assumption is that Arthur is a standard computer (or verifier) equipped with a random number generating device, while Merlin is effectively an oracle with infinite computational power (also known as a prover); but Merlin is not necessarily honest, so Arthur must analyze the information provided by Merlin in response to Arthur's queries and decide the problem itself. A problem is considered to be solvable by this protocol if whenever the answer is "yes", Merlin has some series of responses which will cause Arthur to accept at least 2/3 of the time, and if whenever the answer is "no", Arthur will never accept more than 1/3 of the time. Thus, Arthur acts as a probabilistic polynomial-time verifier, assuming it is allotted polynomial time to make its decisions and queries. ==MA== The simplest such protocol is the 1-message protocol where Merlin sends Arthur a message, and then Arthur decides whether to accept or not by running a probabilistic polynomial time computation. (This is similar to the verifier-based definition of NP, the only difference being that Arthur is allowed to use randomness here.) Merlin does not have access to Arthur's coin tosses in this protocol, since it is a single-message protocol and Arthur tosses his coins only after receiving Merlin's message. This protocol is called ''MA''. Informally, a language ''L'' is in MA if for all strings in the language, there is a polynomial sized proof that Merlin can send Arthur to convince him of this fact with high probability, and for all strings not in the language there is no proof that convinces Arthur with high probability. However, Arthur is not necessarily a BPP verifier as it is not known whether MA is contained in the class .〔https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#existsbpp〕 Formally, the complexity class MA is the set of decision problems that can be decided in polynomial time by an Arthur–Merlin protocol where Merlin's only move precedes any computation by Arthur. In other words, a language ''L'' is in MA if there exists a polynomial-time deterministic Turing machine ''M'' and polynomials ''p'', ''q'' such that for every input string ''x'' of length ''n'' = |''x''|, *if ''x'' is in ''L'', then *if ''x'' is not in ''L'', then The second condition can alternately be written as *if ''x'' is not in ''L'', then To compare this with the informal definition above, ''z'' is the alleged proof from Merlin (whose size is bounded by a polynomial) and ''y'' is the random string that Arthur uses, which is also polynomially bounded. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Arthur–Merlin protocol」の詳細全文を読む スポンサード リンク
|